#include "LinkList.h"
#include <iostream>
LinkList::LinkList():size(0)
{
    head = new Node(0);
}

LinkList::LinkList(const LinkList &list)  //o(n^2)
{
    size = list.size;
    head = new Node(0);
    Node *tp = head;  //遍历指针
    Node *travelPoint = list.head->next;  //遍历指针
    while(travelPoint != nullptr)  //还没有到尾部
    {
        Node *newNode = new Node(travelPoint->value);  //创建一个新的节点
        tp->next = newNode;  //连接
        tp = tp->next;  //移动
        travelPoint = travelPoint->next;  //移动
    }
}

LinkList &LinkList::operator=(const LinkList &list)
{
    while(head != nullptr)
    {
        Node *nextNode = head->next;  //下一个节点存下来
        delete head;
        head = nextNode;
    }
    size = list.size;
    head = new Node(0);
    Node *tp = head;  //遍历指针
    Node *travelPoint = list.head->next;  //遍历指针
    while(travelPoint != nullptr)  //还没有到尾部
    {
        Node *newNode = new Node(travelPoint->value);  //创建一个新的节点
        tp->next = newNode;  //连接
        tp = tp->next;  //移动
        travelPoint = travelPoint->next;  //移动
    }
    return *this;
}

LinkList::~LinkList()
{
    while(head != nullptr)
    {
        Node *nextNode = head->next;  //下一个节点存下来
        delete head;
        head = nextNode;
    }
}

void LinkList::InsertTail(const ElementType &element)  //尾部节点的特征:next指针为空  O(n)
{
    //遍历指针
    Node *travelPoint = head;
    while(travelPoint->next != nullptr)  //还没有到尾部
        travelPoint = travelPoint->next;

    //Node *newNode = new Node(element);  //创建一个新的节点 
    //travelPoint->next = newNode;
    travelPoint->next = new Node(element);  //直接创建新的节点并连接
    size++;
}

void LinkList::InsertHead(const ElementType &element)  //O(1)
{
    Node *newNode = new Node(element);
    newNode->next = head->next;
    head->next = newNode;
    size++;
}

void LinkList::InsertByIndex(size_t index, const ElementType &element)
{
    if(index > size)
    {
        std::cout<<"位置非法!\n";
        return;
    }
    Node *travelPoint = head;
    for(size_t i = 0; i < index; i++)
    {
        travelPoint = travelPoint->next;
    }
    Node *newNode = new Node(element);
    newNode->next = travelPoint->next;
    travelPoint->next = newNode;
    size++;
}

void LinkList::RemoveByIndex(size_t index)  //O(n)
{
    if(index > size)
    {
        std::cout<<"位置不合法!\n";
        return;
    }
    Node *travelPoint = head;
    for(size_t i = 0; i < index; i++)
    {
        travelPoint = travelPoint->next;
    }
    Node *freeNode = travelPoint->next;
    travelPoint->next = freeNode->next;
    delete freeNode;
    size--;
}

void LinkList::RemoveByElement(const ElementType &element)  //O(n)
{
    Node *travelPoint = head;
    while(travelPoint->next != nullptr)
    {
        if(travelPoint->next->value == element)
        {
            Node *freeNode = travelPoint->next;
            travelPoint->next = freeNode->next;
            delete freeNode;
            size--;
        }
        else
            travelPoint = travelPoint->next;
    }
}

ElementType *LinkList::FindByIndex(size_t index)  //O(n)
{
    if(index >= size)
        return nullptr;
    Node *travelPoint = head->next;
    for(size_t i = 0; i < index; i++)
    {
        travelPoint = travelPoint->next;
    }
    return &(travelPoint->value);
}

DARRAY::DynamicArray LinkList::FindByElement(const ElementType &element)
{
    DARRAY::DynamicArray array;
    Node *travelPoint = head->next;
    while(travelPoint != nullptr)
    {
        if(travelPoint->value == element)
        {
            array.InsertTail(&travelPoint->value);
        }
        travelPoint = travelPoint->next;
    }
    return array;
}

void LinkList::UpdateByIndex(size_t index, const ElementType &element)
{
    if(index >= size)
    {
        std::cout<<"位置非法!\n";
        return;
    }
    Node *travelPoint = head->next;
    for(size_t i = 0; i < index; i++)
    {
        travelPoint = travelPoint->next;
    }
    travelPoint->value = element;
}

void LinkList::UpdateByElement(const ElementType &oldValue, const ElementType &newValue)
{
    Node *travelPoint = head->next;
    while(travelPoint != nullptr)
    {
        if(travelPoint->value == oldValue)
        {
            travelPoint->value = newValue;
        }
        travelPoint = travelPoint->next;
    }
}

void LinkList::BubbleSort()
{
    for(size_t i = 0; i < size - 1; i++)
    {
        Node *travelPoint = head;  //每次循环都回到链表的开头
        for(size_t j = 0; j < size - i - 1; j++)
        {
            if(travelPoint->next->value > travelPoint->next->next->value)
            {
                Node *prev = travelPoint->next;
                Node *back = prev->next;   //Node *back = travelPoint->next->next
                prev->next = back->next;
                back->next = prev;
                travelPoint->next = back;
            }
            travelPoint = travelPoint->next;
        }
    }
}

void LinkList::Sort()
{
    FastSort(head->next,nullptr);
}

LinkList LinkList::Merge(const LinkList &list)
{
    LinkList result;
    Node *first = head->next;
    Node *second = list.head->next;
    while(first && second)
    {
        if(first->value < second->value)
        {
            result.InsertTail(first->value);
            first = first->next;
        }
        else
        {
            result.InsertTail(second->value);
            second = second->next;
        }
    }
    while(first)
    {
        result.InsertTail(first->value);
        first = first->next;
    }

    while(second)
    {
        result.InsertTail(second->value);
        second = second->next;
    }
    return result;
}

LinkList LinkList::FindInsertSection(const LinkList &list)
{
    LinkList result;
    Node *first = this->head->next;
    Node *second = list.head->next;
    while(first && second)
    {
        if(first->value == second->value)
        {
            result.InsertTail(first->value);
            first = first->next;
            second = second->next;
        }
        else if(first->value < second->value)
        {
            first = first->next;
        }
        else
        {
            second = second->next;
        }
    }
    return result;
}

LinkList LinkList::FindUnionSection(const LinkList &list)
{
    LinkList result;
    Node *first = this->head->next;
    Node *second = list.head->next;
    while(first && second)
    {
        if(first->value == second->value)
        {
            result.InsertTail(first->value);
            first = first->next;
            second = second->next;
        }
        else if(first->value < second->value)
        {
            result.InsertTail(first->value);
            first = first->next;
        }
        else
        {
            result.InsertTail(second->value);
            second = second->next;
        }
    }
    while(first)
    {
        result.InsertTail(first->value);
        first = first->next;
    }
    while(second)
    {
        result.InsertTail(second->value);
        second = second->next;
    }
    return result;
}

LinkList LinkList::FindDifference(const LinkList &list)
{
    LinkList result;
    Node *first = this->head->next;
    Node *second = list.head->next;
    while (first && second)
    {
        if (first->value == second->value)
        {
            first = first->next;
            second = second->next;
        }
        else if (first->value < second->value)
        {
            result.InsertTail(first->value);
            first = first->next;
        }
        else
        {
            result.InsertTail(second->value);
            second = second->next;
        }
    }
    while (first)
    {
        result.InsertTail(first->value);
        first = first->next;
    }
    while (second)
    {
        result.InsertTail(second->value);
        second = second->next;
    }
    return result;
}

ElementType *LinkList::GetReserveIndex(size_t index)
{
    if(index >= size)
    {
        std::cout<<"位置非法!\n";
        return nullptr;
    }
    Node *slow = head->next;
    Node *fast = slow;
    for(size_t i = 0 ; i < index; i++)
    {
        fast = fast->next;
    }
    while(fast)
    {
        fast = fast->next;
        slow = slow->next;
    }
    return &slow->value;
}

void LinkList::Reserve()
{
    Node *prev = nullptr;
    Node *cur = head->next;
    Node *Next = cur->next;
    while(Next != nullptr)
    {
        cur->next = prev;  //逆序
        prev = cur;
        cur = Next;
        Next = cur->next;
    }
    cur->next = prev;  //最后一个节点单独逆序
    head->next = cur;
}

void LinkList::Reserve2()
{
    head->next = reserve(head->next);
}

void LinkList::show()
{
    std::cout<<"size : "<<size<<std::endl;  //打印链表的大小
    Node *travelPoint = head->next;  //从第一个节点开始
    while(travelPoint != nullptr)  //链表还没有结束
    {
        std::cout<<travelPoint->value<<" ";  //打印节点的值
        travelPoint = travelPoint->next;  //遍历指针往后走
    }
    std::cout<<std::endl;
}

void LinkList::FastSort(Node *start, Node *end)  //快慢指针
{
    if(start == end)
    {
        return ;
    }
    Node *temp = start;  //基准值指针
    Node *slow = start;  //慢指针
    Node *fast = start->next;  //快指针
    while(fast != end)  //快指针没有到结尾
    {
        //  快指针指向的值比基准值小
        if(fast->value < temp->value)
        {
            slow = slow->next;
            std::swap(slow->value,fast->value);  //交换快慢指针的值
        }
        fast = fast->next;
    }
    std::swap(temp->value, slow->value);  //将基准值归位
    FastSort(start,slow);  //[start,slow)
    FastSort(slow->next,end);
}

LinkList::Node *LinkList::reserve(Node *node)
{
    //返回值是原来的尾巴 新链表的头
    if(node->next == nullptr)  //这个节点是尾巴  也是逆序完的头
        return node;
    else
    {
        Node *newHead = reserve(node->next);  //递归往后走
        //逆序核心
        node->next->next = node;
        node->next = nullptr;  //新尾巴  原来的头  指针指向空
        return newHead;
    }
}
